package graph;

import java.util.ArrayList;

/**
 * Class util with methods at graph 
 * @author rocha
 */
public class GraphUtil {

	/**
	 * Verify consistency internal that graph
	 * @param g graph
	 * @return true if graph is valid
	 */
	public static boolean isValidGraph( Graph g ) {
		return false;
	}
	
	/**
	 * acha componentes fortemente conectados de um grafo em O(n*(n + m))
	 * @param g
	 * @return
	 */
	public static boolean profundidade( Graph g ) {
		
		int n = (int) g.getGraph().length;
		
		ArrayList<Boolean> arrayList = new ArrayList<Boolean>();
	 
	    for(int v  = 0; v < n; v++) {
	        dfs(g, v, arrayList);
	    }

	    for(int u =0; u < n; u++) {
	        for(int v=0; v < n; v++) {
	            if (g.getAdjacents(u).get(v) == g.getAdjacents(v).get(u)) {
	                // monstar estrutura floresta
	            }
	        }
	    }
	    
		return false;
	}
	
	@SuppressWarnings("static-access")
	public static void visitor( Graph g, int u, ArrayList<Boolean> arrayList) {
		arrayList.get(u).valueOf( true );
	 
	    for(int i = 0; i < (int)g.getAdjacents(u).size(); i++) {
	        int v = g.getAdjacents(u).get(i);
	        if (!arrayList.get(u)) {
	            visitor(g, v, arrayList);
	        }
	    }
	}

	public static void dfs( Graph g, int u, ArrayList<Boolean> arrayList) {
	    visitor(g, u, arrayList);
	}


	
}